package com.ronz.linkedlist;

import com.ronz.linkedlist.util.HeroNode;
import com.ronz.linkedlist.util.NodeUtil;


/**
 * @Description 合并两个有序链表，要求合并后的链表依然是一个有序的
 * @Author Ronz
 * @Date 2020/12/23 16:02
 * @Version 1.0
 */
public class No5_PenTest_SingleLinkedList {


    public static void main(String[] args) {
        HeroNode node_1 = NodeUtil.getNode_1();
        HeroNode node_2 = NodeUtil.getNode_2();

        HeroNode node = collectList(node_1, node_2);

        HeroNode cur = node.next;
        while (cur != null){
            System.out.println(cur);
            cur = cur.next;
        }
    }

    /**
     * @Description 将 head_1 指向的链表按照结点从小到大顺序合并到 head_2 指向的链表中
     * @Param [head_1, head_2]
     * @return 合并后的有序链表
     */
    public static HeroNode collectList(HeroNode head_1, HeroNode head_2){
        HeroNode cur = head_1.next;
        HeroNode next;
        // 遍历第一个链表，每个元素插入第二个链表中
        while(cur != null){
            next = cur.next;
            insertNode(cur, head_2);
            cur = next;
        }
        return head_2;
    }

    /**
     * @Description 插入一个结点到 head 指向的链表中
     * @Param [node, head]
     * @return void
     */
    public static void insertNode(HeroNode node, HeroNode head){
        HeroNode temp = head;
        while (true){
            if (temp.next == null){
                // 说明遍历到了链表的末尾，直接追加即可
                temp.next = node;
                node.next = null;
                break;
            }
            if (temp.next.getNo() > node.getNo()){
                // 如果该结点小于了要插入的链表的结点，那么就把这个结点插入到第一个小于的结点的前一个
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }
}
